package com.lwl.leetcode;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/9/29 17:05
 */
public class Code32LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        char[] charArray = s.toCharArray();
        int res = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == '(' || i == 0) {
                continue;
            }
            if (charArray[i - 1] == '(') {
                dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
            } else if (i - dp[i - 1] - 1 >= 0 && charArray[i - dp[i - 1] - 1] == '(') {
                dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 : dp[i - 1] + 2;
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int longestValidParentheses1(String s) {
        char[] charArray = s.toCharArray();
        LinkedList<Integer> stack = new LinkedList<>();
        stack.addLast(-1);
        int res = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == '(') {
                stack.addLast(i);
            } else {
                if (stack.isEmpty()) {
                    stack.addLast(i);
                } else {
                    int lastIndex = stack.pollLast();
                    if (lastIndex == -1) {
                        stack.addLast(i);
                    } else if (charArray[lastIndex] == '(') {
                        // 可以匹配上, 此时的 stack 不可能为空
                        res = Math.max(res, i - stack.peekLast());
                    } else {
                        stack.addLast(i);
                    }
                }
            }
        }
        return res;
    }
}
